// 给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。
// 另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。
// 返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，
// 其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。
// （你可以按任何满足此条件的顺序返回答案。）

const allCellsDistOrder = function (R: number, C: number, r0: number, c0: number): number[][] {
    const res: number[][] = [
        [r0, c0]
    ]; // 结果数组
    const queue: number[][] = [
        [r0, c0]
    ];// BFS队列
    const hashSet = new Set<string>();// 哈希集合
    hashSet.add(r0 + ',' + c0);// 初始化坐标
    const directives: number[][] = [
        [0, 1],
        [0, -1],
        [1, 0],
        [-1, 0]
    ]; // 方向向量
    // 广度优先遍历过程
    while (queue.length > 0) {
        let currLen: number = queue.length;
        for (let i = 0; i < currLen; i++) {
            const origin: number[] = queue.shift()!;// 出队原始坐标
            for (let directive of directives) {
                let currX: number = origin[0] + directive[0];
                let currY: number = origin[1] + directive[1];
                // 边缘检测
                if (currX >= 0 && currX < R && currY >= 0 && currY < C) {
                    let key: string = currX + ',' + currY;
                    // 判断当前坐标是否访问过
                    if (!hashSet.has(key)) {
                        hashSet.add(key);
                        queue.push([currX, currY]);
                        res.push([currX, currY]);
                    }
                }
            }
        }
    }
    return res;
};

allCellsDistOrder(2, 2, 0, 1)

// 计算曼哈顿距离
// function allCellsDistOrder_calDis(pointA, pointB) {
//     return Math.abs(pointA[0] - pointB[0]) + Math.abs(pointA[1] - pointB[1]);
// }

// 这道题目也是建议在纸上画一画，其实相通之后并不难
// 关键之处是在于需要搞明白曼哈顿距离和我们传统直观感受的距离有什么不同
// 区别之处在于你要想清楚正方形端点处和中点处的曼哈顿距离是一样的（画个图理解）
// 所以其实可以把所有的坐标看作树的结点，距离相等的结点位于树的同一层
// 而对于每一层的结点，它们的距离 dist 可以分为行距离和列距离，且 rowDist + colDist = dist 必然成立
// 所以我们就可以使用BFS求解了
// 而且使用BFS不需要关心最大距离，也不需要计算曼哈顿距离，只要所有点都完成检索就可以终止搜索
// 但此解法中每种距离可能产生多个不在矩阵内的坐标，但搜索算法必须依次检查予以排除